/*
 * Copyright (c) 2021
 * User:LENOVO
 * File:合并两个有序链表.java
 * Date:2021/02/18 14:18:18
 */

package org.bytedance.链表和数;

import com.alibaba.fastjson.JSONObject;

import java.util.ArrayList;
import java.util.List;

/**
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * <p>
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * <p>
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 */
public class 合并两个有序链表 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(4);

        ListNode node2 = new ListNode(1);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(4);

        List<Integer> res = mergeTwoLists(node1, node2);
        System.out.println(JSONObject.toJSONString(res));

        node1 = null;
        node2 = null;
        res = mergeTwoLists(node1, node2);
        System.out.println(JSONObject.toJSONString(res));

        node2 = new ListNode(0);
        res = mergeTwoLists(node1, node2);
        System.out.println(JSONObject.toJSONString(res));

        node1 = new ListNode(1);
        node1.next = new ListNode(2);
        node1.next.next = new ListNode(4);

        node2 = new ListNode(1);
        node2.next = new ListNode(3);
        node2.next.next = new ListNode(4);


        ListNode listNode = mergeTwoLists2(node1, node2);
        printListNode(listNode);

    }

    private static void printListNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.value + " ");
            listNode = listNode.next;
        }
    }

    private static class ListNode {
        int value;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.value = val;
        }

        ListNode(int val, ListNode next) {
            this.value = val;
            this.next = next;
        }
    }

    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.value < l2.value) {
            l1.next = mergeTwoLists2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }

    public static List<Integer> mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode h1 = l1, h2 = l2;
        List<Integer> res = new ArrayList<>();
        if (h1 == null) return res;
        if (h2 == null) return res;
        ListNode newHead = null, curNode = null;
        while (h1 != null && h2 != null) {
            int v1 = h1.value, v2 = h2.value;
            if (v1 == v2) {
                /*if (curNode != null) {
                    curNode.next = h1;
                    curNode = h1;
                    curNode.next = h2;
                    curNode = h2;
                } else {
                    curNode = h1;
                    newHead = curNode;
                    curNode.next = h2;
                    curNode = h2;
                }*/
                ListNode tmp1 = h1;
                ListNode tmp2 = h2;
                res.add(h1.value);
                res.add(h2.value);
                h1 = h1.next;
                h2 = h2.next;
                if (curNode != null) {
                    curNode.next = tmp1;
                    curNode = tmp1;
                    curNode.next = tmp2;
                    curNode = tmp2;
                } else {
                    newHead = tmp1;
                    curNode = tmp1;
                    curNode.next = tmp2;
                    curNode = tmp2;
                }
            } else if (v1 < v2) {
                if (curNode != null) {
                    curNode.next = h1;
                    curNode = h1;
                } else {
                    curNode = h1;
                    newHead = curNode;
                }
                res.add(h1.value);
                h1 = h1.next;
            } else {
                if (curNode != null) {
                    curNode.next = h2;
                    curNode = h2;
                } else {
                    curNode = h2;
                    newHead = curNode;
                }
                res.add(h2.value);
                h2 = h2.next;
            }
        }
        if (h1 != null) {
            curNode.next = h1;

        }

        if (h2 != null) {
            curNode.next = h2;
        }
        return res;
    }


}
